package com.dyz.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LongestConsecutive128 {
    public int longestConsecutive(int[] nums) {
        //使用HashMap的方式，以空间换时间
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            if(map.containsKey(num)){continue;}
            int left = map.get(num-1)!=null?map.get(num-1):0;
            int right = map.get(num+1)!=null?map.get(num+1):0;
            if(left>0&&right>0){
                map.put(num-left, left+right+1);
                map.put(num+right, left+right+1);
                map.put(num,1);
            }else if(left>0){
                map.put(num-left,left+1);
                map.put(num, left+1);
            }else if(right>0){
                map.put(num+right, right+1);
                map.put(num, right+1);
            }else {
                map.put(num, 1);
            }
        }
        int res = 0;
        for(int in:map.values()){
            res = Math.max(in, res);
        }
        return res;
    }

    public int longestConsecutive1(int[] nums) {
        //空间换时间
        Set<Integer> numsSet = new HashSet<>();
        for (Integer num : nums) {
            numsSet.add(num);
        }
        int longest = 0;
        for (Integer num : nums) {
            if (numsSet.remove(num)) {
                // 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
                int currentLongest = 1;
                int current = num;
                while (numsSet.remove(current - 1)) current--;
                currentLongest += (num - current);
                // 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
                current = num;
                while(numsSet.remove(current + 1)) current++;
                currentLongest += (current - num);
                // 搜索完后更新longest.
                longest = Math.max(longest, currentLongest);
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,3,7,2,5,8,4,6,0,1};
        int i = new LongestConsecutive128().longestConsecutive1(nums);
        System.out.println(i);

    }
}
